1. Field of the Invention
The present invention relates to the field of pedestrian navigation, based at least partially on a so-called xe2x80x9cdead reckoningxe2x80x9d (DR) approach, in which the evolving position of a pedestrian is determined from within his or her frame of reference. In other words, navigation by DR does not rely on means which use external positional references, such as GPS (global positioning by satellite), rangefinders, etc. It can however make use of the Earth""s magnetic field to determine a compass bearing. Navigation by dead reckoning is required when external position references are not available or exploitable. For instance, GPS data cannot reach a pedestrian in surroundings at least partially hidden from elevational lines of sight: buildings, shadowed zones, dense forests, etc. or in case of jamming. GPS data can be used to complement dead reckoning data and also to establish initial calibration and parameterization.
2. Prior Art
Pedestrian navigation by DR is generally based on the detection of body movements during walking. A classical pedometer is one example based on such an approach, where a harmonic motion of a limb is used to count steps. The step count can then be multiplied by a computed stride length to yield an approximate estimate of a total traveled distance. However, a simple pedometer cannot indicate the pedestrian""s net displacement in a random walk situation, as the direction of motion is not detected.
More sophisticated pedestrian DR navigation systems aim to estimate walking speed and direction in a combined manner to provide an indication of a net displacement from a known reference point. They also take into account the fact that the stride length varies with walking speed, and cannot be used as a constant factor, as in the case of a simple pedometer.
An example of such a system is disclosed in patent document U.S. Pat. No. 5,583,776 to Levi and Judd. Here, an accelerometer is used to provide acceleration data indicative of footsteps. Specifically, the accelerometer is set to measure a periodic variation in the vertical direction (i.e. in the head-foot alignment). A waveform analysis algorithm based on Fourier analysis is used to detect peaks in the vertical acceleration, these establishing the step frequency. The distance traveled is then derived on the basis of an initial calibration phase, in which a correspondence is established between the pedestrian""s walking speed and the fundamental frequency of the vertical acceleration peaks in the frequency spectrum. North and East accumulators are used to track the evolution in direction with the distance traveled.
The vertical acceleration is produced by foot impacts with the ground. This means that the frequency spectrum from the accelerometer varies not only from one person to another, but also on ground conditions. The latter thus constitute an additional variable parameter that must be accommodated by the algorithm. Limits are quickly reached, however, and reliable navigation cannot be expected when the pedestrian is on soft or uneven ground (e.g. muddy fields, gravel, rubble, etc.). Under such conditions, steps can be missed out or over-counted, giving rise to accumulated errors quickly rising to unacceptable levels.
Reliance on vertical acceleration can also lead to false step detection when the pedestrian is jumping on the spot.
Moreover, vertical acceleration data alone does not provide a distinction between normal forward motion steps and backward steps. In other words, it cannot resolve forward/backward motion ambiguity in the pedestrian""s step directions. Similarly, vertical acceleration data alone cannot serve to detect side stepping motion, let alone distinguish between left and right side steps. This can be an important drawback for pedestrians such as infantrymen, firefighters, sportsmen, people walking through crowds, cluttered environments, etc. who may be expected to make backward and side movements.
Moreover, vertical acceleration data does not provide a means for identifying steps when climbing up or down stairs in the state of the art.
Finally, useful vertical acceleration data is clearly absent when the pedestrian is effecting a crawling movement.
It is an object of the present invention to provide a means of pedestrian navigation by dead reckoning (DR), which does not suffer the drawbacks of prior art approaches based on vertical acceleration measurements as the sole source of acceleration data.
The invention thus proposes a new approach to pedestrian navigation which either does not make use of vertical acceleration data, or else uses vertical acceleration, but in conjunction with non-vertical acceleration data, the former complementing the latter.
It is also an object of the invention to provide a compact and highly accurate dead reckoning mode pedestrian navigation apparatus by making use of standard miniaturized inertial navigation system (INS) modules as a source of accelerometric signals. In accordance with this aspect of the invention, one or more signal outputs of an INS module (typically corresponding to three orthogonal axes) is/are analyzed for peak detection, as opposed to being integrated in time in the case of a normal INS application for vehicle navigation. This way of exploiting an INS module output is advantageous from the point of view of miniaturization, economics, accuracy and reliability. It also makes it possible to exploit other sensing devices contained in commercially available INS modules, such as gyroscopes or a digital magnetic compass, temperature or pressure sensors, processor, etc. for realizing the pedestrian navigation apparatus according to the invention. When such an INS module is thus implemented in accordance with the invention, it shall be referred to as a xe2x80x9cpedestrian navigation systemxe2x80x9d (PNS) module.
According to a first aspect, the invention proposes method of determining a displacement of a pedestrian by detecting accelerations of the pedestrian, the method comprising the steps of:
detecting accelerations along a direction which is substantially non-vertical,
determining at least one characteristic feature of the detected accelerations correlated with a displacement step motion, and
determining the displacement on the basis of the determined characteristic feature(s).
The term vertical refers to the direction given by a plumb line, following the usual definition.
Preferably, as will appear further, the accelerations are detected along a direction which is substantially perpendicular to the vertical direction.
The characteristic determination step may comprise the sub-steps of:
detecting a repetition of a the characteristic feature in the accelerations,
measuring a time interval separating a currently detected and a previously detected the characteristic feature, and
determining whether the time interval falls within at least one of an upper and a lower limit,
wherein the displacement determining step comprises the step of considering the currently detected characteristic feature as corresponding to a displacement step if the time interval falls within the limit(s).
the characteristic feature can be a maximum acceleration value or a minimum acceleration value in a determined group of detected acceleration values acquired in a time window.
The acceleration is preferably detected along an antero-posterior (forward-backward) direction of the pedestrian and, depending on the algorithm used, possibly also along a lateral (left-right) direction of the pedestrian.
The step characteristic feature determining step preferably involves determining a peak acceleration from the detected accelerations and correlating the peak with a motion of the body corresponding to a displacement.
The method may further comprise the step of detecting whether the pedestrian is moving or not, the determining step comprising:
acquiring acceleration values during a time interval,
calculating a variance in the acquired acceleration values, comparing the variance to a determined threshold, and
considering that the pedestrian is moving if the variance is superior to the threshold,
It may also further comprise determining a direction, relative to the pedestrian, of a detected step.
In this connection, there can be provided a step of distinguishing between whether the pedestrian is making a step in an antero-posterior sense (forward or backward direction) on the one hand, and in a lateral sense (left or right direction) on the other, the distinguishing step comprising:
determining a variance of successive acceleration values over a given time period for both an acceleration in the antero-posterior sense and in the lateral sense,
comparing the variance determined for the antero-posterior acceleration values with the variance determined for the lateral acceleration values,
determining that the pedestrian is making a step in the antero-posterior sense if the variance of the antero-posterior acceleration values exceeds the variance of the lateral acceleration values, and
determining that the pedestrian is making a step in the lateral sense if the variance of the lateral acceleration values exceeds the variance of the antero-posterior acceleration values.
There can also be provided a step of distinguishing between forward and backward steps relative to the pedestrian, the distinguishing step comprising:
detecting accelerations along an antero-posterior (forward-backward) direction relative to the pedestrian,
determining a time of occurrence of a current first characteristic value and a previous first characteristic value in the antero-posterior accelerations,
determining whether a time interval separating the current and previous first characteristic values is within determined time limits,
determining a time of occurrence of a second characteristic value in the antero-posterior accelerations occurring within a time range at least sufficiently large to contain the determined time limits, and
discriminating between a forward and a backward step on the basis of the order of occurrence of the current first characteristic value and the second characteristic value.
In the above case, the first characteristic value can be a maximum value in a group of detected acceleration values, and the second characteristic value a minimum value of the detected accelerations, the displacement step being determined as corresponding to a forward displacement step if the minimum value precedes the maximum value, and as corresponding to a backward step if the maximum value precedes the minimum value.
Similarly, the method may comprise a step of distinguishing between left and right displacement steps relative to the pedestrian, the distinguishing step comprising:
detecting accelerations along a lateral (left-right) direction relative to the pedestrian,
determining a time of occurrence of a current first characteristic value and a previous first characteristic value in the lateral accelerations,
determining whether a time interval separating the current and previous first characteristic values is within determined time limits,
determining a time of occurrence of a second characteristic value in the lateral accelerations occurring within a time range at least sufficiently large to contain the determined time limits, and
discriminating between a left and a right step on the basis of the order of occurrence of the current first characteristic value and the second characteristic value.
Likewise, the first characteristic value can be a maximum value in a group of detected acceleration values, and the second characteristic value can be a minimum value of the detected accelerations, the displacement step being determined as corresponding to a right displacement step if the minimum value precedes the maximum value, and as corresponding to a left displacement step if the maximum value precedes the minimum value.
The acceleration detecting step can also further comprise detecting accelerations along the vertical direction.
The characteristic determination step can comprise the sub-steps of:
determining a first time corresponding to an occurrence of a characteristic feature in the accelerations along a direction substantially perpendicular to a vertical direction of the pedestrian,
detecting accelerations along a vertical direction of the pedestrian,
determining a second time corresponding to an occurrence of the characteristic feature in the accelerations along a vertical direction of the pedestrian,
comparing the first and second times, and
using a result of the comparison to confirm the presence of a displacement step.
In this case, the characteristic feature can be a maximum acceleration value in a determined group of detected acceleration values.
In one embodiment, a step direction in at least one of an antero-posterior (forward-backward) sense and a lateral (left-right) sense is distinguished using a model adapted to recognize patterns in detected acceleration values that are representative of specific step directions. The model in question can be a Hidden Markov Model.
Advantageously,
the acceleration detecting step comprises acquiring successive acceleration values,
the characteristic and displacement determination steps comprise the sub-steps of:
determining a current peak acceleration in the successive acceleration values by means of a sliding window,
determining a variance of the successive acceleration values acquired between the current peak and a previous peak acceleration value,
comparing the variance to an adaptive threshold to detect if the pedestrian is walking or not,
determining whether the time interval between two successive peak acceleration values falls within a physiologically possible time interval, and
storing the time of acquisition of the current peak acceleration value as the time of occurrence of a detected foot impact corresponding to a displacement step.
The displacement determining step can involve determining a distance traveled by using at least one first model which yields a pedestrian displacement speed in response to a variance and/or a frequency of occurrence of the characteristic feature in values of the acquired accelerations, and at least a time indicator or a second model which correlates a pedestrian displacement speed obtained by the first model with a step length.
The first mathematical model can correlate displacement speed with the variance in accordance with the following relationship:
2-dimensional relative speed=D*(variance)E+F*frequency of steps where D, E and F are numerical coefficients from which D and F can be set equal to 0 or a finite value, 2-dimensional displacement speed being obtained by multiplying the 2-dimensional relative speed by stature or the leg length according to the model which is chosen and 3-dimensional displacement speed then being computed by adding the vertical displacement vbaro to the 2-dimensional displacement speed.
It may also correlate displacement speed with either the variance or a frequency of occurrence of the characteristic feature in accordance with the following relationship:
2-dimensional relative speed=A*(Frequency or Variance)B+C, where AB, and C are numerical coefficients. Relative speed is determined by dividing the velocity by stature or by leg-length, according to the model which is chosen, 2-dimensional displacement speed being obtained by multiplying the 2-dimensional relative speed by stature or the leg length according to the model which is chosen and 3-dimensional displacement speed then being computed by adding the vertical displacement vbaro to the 2-dimensional displacement speed.
The time indicator can correspond to a time interval between two successive said characteristic features, whereby:
step length=speed*time between two successive characteristic features
The second mathematical model can correlate step length with displacement speed in accordance with the following relationship:
step length=s10+mxc3x97displacement speed;
where s10 is a fraction of the step length which is constant and independent of speed of progression, and m is a slope of a function describing the step length as a function of displacement speed.
An initial s10 value is preferably determined with different model for a male or a female pedestrian.
There can be further provided the step of updating at least one parameter of the second mathematical model on the basis of external positioning data, such as data from a global positioning by satellite (GPS) system.
The displacement determining step can involve calculating a displacement on foot and/or a displacement speed of the pedestrian.
Preferably, the method comprises the step of azimuth computation for each step or group of steps effected to determine a position of the pedestrian.
An azimuth computation can be computed for each determined displacement step, the computation e.g. comprising the steps of:
distinguishing a direction of a step between forward, backward, left and right displacement steps,
detecting an azimuth from a sensor carried by the pedestrian,
correcting the detected azimuth with bias and an offset angle in accordance with a distinguished of step.
In the above case, the azimuth computation can be performed from azimuth signals produced by magnetic sensor means or by magnetic sensor means yielding raw angular data signals, the step comprising a sub step of extracting the cosine and sine components of the raw azimuth data and filtering the cosine and sine components.
The azimuth computation can also be performed from azimuth signals produced by a gyroscopic sensor.
In one embodiment where the azimuth computation is performed by magnetic sensor means and by other sensor means not dependent on the North magnetic field, such as gyroscope means, the method may further comprise the steps:
comparing azimuth readings from the magnetic and the other sensor means, and
ignoring azimuth readings from the magnetic sensor means if the comparison step reveals a discrepancy between the readings exceeding a limit value, indicative of a significant magnetic disturbance.
Advantageously, there is further provided a step of detecting an about turn in a displacement of the pedestrian, comprising:
detecting a condition in which an azimuth rate of change of the pedestrian exceeds a determined threshold,
determining whether the azimuth rate of change corresponds roughly to a 180xc2x0 turn,
in the affirmative, determining whether alignments of trajectories before and after the turn are the same to within a determined discrepancy limit,
in the affirmative, considering that an about turn is effected.
In the above procedure, any step made during a period in which the azimuth rate of change exceeds the determined threshold is preferably not used to calculate a distance of displacement.
An azimuth in the above procedure can be calculated on the basis of an average between the alignments corresponding to a forward and return path.
The about turn can be considered to be effected only on the further condition that the azimuth measured after the determined turn is 180xc2x0 different respect to the other. The person is considered as going back on his or her footsteps only while the trajectory effected after the azimuth rate of change of the pedestrian exceeds a determined threshold is statistically shorter than or equal to a trajectory effected before the azimuth rate of change of the pedestrian exceeds a determined threshold.
The method can further comprise the step of acquiring barometer data to determine an elevational component in the determined displacement.
Satellite positioning means can also be used to correct displacement information obtained through the accelerations.
The accelerations can be detected by acceleration sensor means mounted on the waist or trunk of the pedestrian.
The accelerations can be detected by using sensors of an inertial navigation system (INS). These can housed in a module together with azimuth detection means, the azimuth detection means being one of a magnetometer means and gyroscope means, and being used to acquire azimuth data.
The accelerations can be detected by means of three mutually orthogonal acceleration sensors each delivering an acceleration component of a respective orthogonal axis on a separate channel.
More economical embodiments of the invention can be contemplated, in which the accelerations are detected by means of two mutually orthogonal acceleration sensors each delivering an acceleration component operatively aligned along a respective orthogonal axis, the alignment of at least one of the sensors having a component in a non vertical direction when operatively carried by the pedestrian.
In the above two-sensor embodiment, at least one the axis of an accelerometer is preferably inclined with respect to a vertical axis of the pedestrian.
According to a second aspect, the invention provides a method of pedestrian navigation operative in a dead reckoning mode, comprising the steps of:
detecting an evolving signal indicative of accelerations of the pedestrian in the antero-posterior (forward-backward) direction,
analyzing the signals to determine a variation therein conforming to predetermined constraints,
using the variation to establish a displacement step motion and to determine displacement information comprising at least one of a speed and distance of displacement,
determining an azimuth of the pedestrian, and
combining the displacement data with the azimuth to obtain pedestrian navigation information.
According to a third aspect, the invention provides a method of pedestrian navigation operative in a dead reckoning mode, comprising the steps of:
using an Inertial Navigation System (INS) as a source acceleration signals, the system having a motion detection sensor responsive to accelerations along the antero-posterior (forward-backward) direction of the pedestrian,
submitting signals from the INS to a waveform analysis to determine a step of the pedestrian, and
determining pedestrian navigation information on the basis of the waveform analysis.
The INS may also have a motion sensor responsive to accelerations along a lateral (left-right) direction of the pedestrian, signals therefrom being submitted to a waveform analysis to determine a left or right displacement effected by the pedestrian.
The INS may also have a motion sensor responsive to accelerations along a vertical direction of the pedestrian, signals therefrom being submitted to a waveform analysis to provide a confirmation of a determination of a displacement step.
The INS may further comprise bearing detection means in the form of magnetometer means and/or gyroscope means, the means being used to obtain an azimuth of the pedestrian for the determination of the navigation information.
The INS can be in the form of a module carried on the waist or trunk of the pedestrian.
According to a fourth aspect, the invention provides an apparatus for determining a displacement of a pedestrian by detecting accelerations of said pedestrian, said apparatus comprising:
sensing means for detecting accelerations along a direction which is substantially non vertical,
characteristic determining means for determining at least one characteristic feature of said detected accelerations correlated with a displacement step motion, and
displacement determining means for determining said displacement on the basis of said determined characteristic feature(s).
According to a fifth aspect, the invention provides an apparatus for pedestrian navigation operative in a dead reckoning mode, comprising:
means for detecting an evolving signal indicative of accelerations of said pedestrian in the antero-posterior (forward-backward) direction,
means for analyzing said signals to determine a variation therein conforming to predetermined constraints,
means using said variation to establish a displacement step motion and to determine displacement information comprising at least one of a speed and distance of displacement,
means for determining an azimuth of said pedestrian, and
means for combining said displacement data with said azimuth to obtain pedestrian navigation information.
According to a sixth aspect, the invention provides an apparatus for pedestrian navigation operative in a dead reckoning mode, comprising:
an Inertial Navigation System (INS) serving as a source acceleration signals, said system having a motion detection sensor aligned along the antero-posterior (forward-backward) direction of said pedestrian,
means for submitting signals from said INS to a waveform analysis to determine a step of said pedestrian, and
means for determining pedestrian navigation information on the basis of said waveform analysis.
It shall be noted that the optional aspects of the invention presented above in the context of the method apply mutatis mutandis to the apparatus forms of the invention.